package com.LeetCode.why112;

import com.LeetCode.why98.TreeNode;

import java.util.Stack;


public class PathSum {
    class Solution {
        //中规中矩的用栈解决二叉树深度遍历
        class SumToNow {
            TreeNode ele;
            int sum;

            SumToNow(TreeNode ele, int sum) {
                this.ele = ele;
                this.sum = sum;
            }
        }

        public boolean hasPathSum(TreeNode root, int sum) {
            Stack<SumToNow> st = new Stack<SumToNow>();
            if (root != null) {
                st.push(new SumToNow(root, 0));
            }
            while (!st.empty()) {
                SumToNow tmp = st.pop();
                TreeNode tmpTree = tmp.ele;
                int tmpSum = tmpTree.val + tmp.sum;
                if (tmpTree.left != null) {
                    st.push(new SumToNow(tmpTree.left, tmpSum));
                }
                if (tmpTree.right != null) {
                    st.push(new SumToNow(tmpTree.right, tmpSum));
                }
                if (tmpTree.left == null && tmpTree.right == null && tmpSum == sum) {
                    return true;
                }
            }


            return false;
        }
    }
}
